package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.BinaryTreeNode;

import java.util.Locale;

/**
 * 二叉树的下一个节点
 *
 * @author yuhushuan
 * @date 2020/6/2 01:28
 */
public class _08_1_NextNodeInBinaryTrees {

    private static BinaryTreeNode getNext(BinaryTreeNode node) {
        if (node == null) {
            return null;
        }

        BinaryTreeNode next = null;
        // 如果一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点
        if (node.right != null) {
            BinaryTreeNode right = node.right;
            while (right.left != null) {
                right = right.left;
            }
            next = right;
        } else if (node.parent != null) {// 没有右子树
            BinaryTreeNode current = node;
            BinaryTreeNode parent = node.parent;
            while (parent != null && current == parent.right) {// g 的下一个节点应该返回 null
                current = parent;
                parent = parent.parent;
            }
            next = parent;
        }
        return next;
    }


    // ==================== 辅助代码用来构建二叉树 ====================

    private static void connectTreeNodes(BinaryTreeNode parent, BinaryTreeNode left, BinaryTreeNode right) {
        if (parent != null) {
            parent.left = left;
            parent.right = right;

            if (left != null) {
                left.parent = parent;
            }
            if (right != null) {
                right.parent = parent;
            }
        }
    }

    /**
     * 1
     * 2          3
     * 4   5      6   7
     * 8  9
     * <p>
     * 中序：4 2 8 5 9 1 6 3 7
     */
    private static void test1() {
        BinaryTreeNode a = new BinaryTreeNode(1);
        BinaryTreeNode b = new BinaryTreeNode(2);
        BinaryTreeNode c = new BinaryTreeNode(3);
        BinaryTreeNode d = new BinaryTreeNode(4);
        BinaryTreeNode e = new BinaryTreeNode(5);
        BinaryTreeNode f = new BinaryTreeNode(6);
        BinaryTreeNode g = new BinaryTreeNode(7);
        BinaryTreeNode h = new BinaryTreeNode(8);
        BinaryTreeNode i = new BinaryTreeNode(9);

        connectTreeNodes(a, b, c);

        connectTreeNodes(b, d, e);

        connectTreeNodes(e, h, i);

        connectTreeNodes(c, f, g);

        System.out.println("二叉树的中序遍历：");
        BinaryTreeNode.inOrderTraversal_Recursively(a);
        System.out.println();

        print(a);
        print(c);
        print(i);
        print(g);
    }


    private static void print(BinaryTreeNode node) {
        BinaryTreeNode next = getNext(node);

        if (next == null) {
            System.out.println(String.format(Locale.getDefault(),
                    "节点 %d 没有下一个节点",
                    node.value));
        } else {
            System.out.println(String.format(Locale.getDefault(),
                    "节点 %d 的下一个节点是 %d",
                    node.value, next.value));
        }
    }

    public static void main(String[] args) {
        test1();
    }

}
